/*
1. 状态定义：

定义了3个明确的状态：
状态0：在连续1区间之前（必须全0）
状态1：在连续1区间中（可以有1）
状态2：在连续1区间之后（必须全0）
2. 状态转移：

每个字符的处理都基于前一个字符的状态
状态转移遵循严格的规则：
从状态0只能转移到状态0或状态1
从状态1可以转移到状态1或状态2
从状态2只能保持在状态2
3. 状态机特性：

明确的有限状态集合
状态转移由当前输入字符决定
每个状态有明确的含义和限制条件
4. DP特性：

保存中间结果（dp数组）
通过子问题的解构建最终解
自底向上的求解方式
这个实现结合了状态机和动态规划的特点，是典型的状态机DP解决方案。它通过定义状态和状态转移规则，系统地探索所有可能的解空间，找到最优解。

状态机DP特别适合这种需要跟踪特定模式或序列的问题，因为它可以明确地建模问题中的不同阶段或状态。
*/


// 状态机dp
#pragma GCC optimize(2, "Ofast", "inline")
#include <iostream>
#include <algorithm>
#include <climits>
#define endl '\n'
using namespace std;

int t, n;
string s;
int dp[200005][3];  // 0: 连续1的区间前(必须全0), 1: 连续1的区间中(必须全1), 2: 连续1的区间后(必须全0)

void solve() 
{
    // 初始化
    dp[0][0] = (s[0] == '1');  // 在区间前，如果是1需要变成0
    dp[0][1] = (s[0] == '0');  // 在区间中，如果是0需要变成1
    dp[0][2] = INT_MAX;        // 在区间后，第一个字符不能在区间后

    for (int i = 1; i < n; i++) 
    {
        // i号有三种可能，有可能是在连续1区间前，有可能是在连续1区间中，有可能是在连续1区间后
        // 状态0: 在区间前，必须保持0
        dp[i][0] = dp[i - 1][0] + (s[i] == '1');
        // 状态1: 在区间中，可以来自状态0或状态1
        dp[i][1] = min(dp[i - 1][0], dp[i - 1][1]) + (s[i] == '0');
        // 状态2: 在区间后，可以来自状态1或状态2，必须保持0
        dp[i][2] = min(dp[i - 1][1], dp[i - 1][2]) + (s[i] == '1');
    }
    // 最终结果可以是状态0、1或2中的最小值
    cout << min({ dp[n - 1][0], dp[n - 1][1], dp[n - 1][2] }) << endl; 
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> t;
    while (t--) 
    {
        cin >> n >> s;
        solve();
    }
    return 0;
}